package com.squirrel.michale;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/3/7 6:56 AM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode2101 {

    // 知道了什么是KD树，有时间在学习。先暴力解题。
    public int maximumDetonation(int[][] bombs) {
        int n = bombs.length;
        List<List<Integer>> bombList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            List<Integer> trigger = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    long deltaX = bombs[i][0] - bombs[j][0];
                    long deltaY = bombs[i][1] - bombs[j][1];
                    long r = bombs[i][2];
                    if (deltaX * deltaX + deltaY * deltaY <= r * r) {
                        trigger.add(j);
                    }
                }
            }
            bombList.add(trigger);
        }

        int result = 0;
        for (int i = 0; i < n; i++) {
            boolean[] visited = new boolean[n];
            Queue<Integer> queue = new ArrayDeque<>();
            queue.offer(i);
            visited[i] = true;
            int count = 1;
            while (!queue.isEmpty()) {
                int start = queue.poll();
                for (int next : bombList.get(start)) {
                    if (!visited[next]) {
                        queue.offer(next);
                        visited[next] = true;
                        count++;
                    }
                }
            }
            result = Math.max(result, count);
        }
        return result;
    }


    public int maximumDetonation2(int[][] bombs) {
        int n = bombs.length;
        List<List<Integer>> bombList = new ArrayList<List<Integer>>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                long deltaX = bombs[i][0] - bombs[j][0];
                long deltaY = bombs[i][1] - bombs[j][1];

                long r = bombs[i][2];

                List<Integer> trigger = new ArrayList<>();
                if (deltaX * deltaX + deltaY * deltaX <= r * r) {

                    trigger.add(j);

                }
                bombList.add(trigger);
            }
        }

        int result = 0;
        for (int i = 0; i < n; i++) {
            boolean[] visited = new boolean[n];
            Queue<Integer> queue = new ArrayDeque<Integer>();
            queue.offer(i);
            visited[i] = true;
            while (!queue.isEmpty()) {
                int start = queue.poll();
                for (int next : bombList.get(start)) {
                    if (visited[next]) {
                        continue;
                    }
                    queue.offer(next);
                    visited[i] = true;
                }
            }

            int count = 0;
            for (int j = 0; j < n; j++) {
                count += visited[j] ? 1 : 0;
            }
            result = Math.max(result, count);
        }
        return result;

    }


    public static void main(String[] args) {
//        [[1,1,5],[10,10,5]]
//        输出
//        2
//        预期结果
//        1

        LeetCode2101 leetCode2101 = new LeetCode2101();

        int[][] bombs = new int[][]{{2,1,3},{6,1,4}};
        System.out.println(leetCode2101.maximumDetonation(bombs));

        int[][] bombs2 = new int[][]{{1, 1, 5}, {10, 10, 5}};
        System.out.println(leetCode2101.maximumDetonation(bombs2));


        int[][] bombs3 = new int[][]{{1, 2, 3}, {2, 3, 1}, {3, 4, 2}, {4, 5, 3}, {5, 6, 4}};
        System.out.println(leetCode2101.maximumDetonation(bombs3));


        int[][] bombs4 = new int[][]{{1, 1, 100}, {81, 61, 60}};
        System.out.println(leetCode2101.maximumDetonation(bombs4));
        // 2

    }

}
